import random
import math

def assign_cluster(x, c):

    min_dist = float('inf')
    cluster_idx = 0
    for i, center in enumerate(c):
        # 计算欧氏距离
        dist = math.sqrt(sum([(a - b) ** 2 for a, b in zip(x, center)]))
        if dist < min_dist:
            min_dist = dist
            cluster_idx = i
    return cluster_idx

def Kmeans(data, k, epsilon, iteration):
   
    # 输入检查
    if not data:
        raise ValueError("数据不能为空")
    if k <= 0 or k > len(data):
        raise ValueError(f"k值必须在1到{len(data)}之间")
    if iteration <= 0:
        raise ValueError("迭代次数必须为正整数")

    # 初始化聚类中心：随机选择k个不重复样本
    n_samples = len(data)
    centers = random.sample(data, k)
    prev_centers = None
    labels = [0] * n_samples  # 记录每个样本的聚类标签

    for _ in range(iteration):
        # 分配样本到最近的聚类中心
        for i, sample in enumerate(data):
            labels[i] = assign_cluster(sample, centers)

        # 更新聚类中心
        new_centers = []
        for i in range(k):
            # 找到当前聚类的所有样本
            cluster_samples = [data[j] for j in range(n_samples) if labels[j] == i]
            if not cluster_samples:  # 避免空聚类（重新随机选择一个中心）
                new_center = random.choice(data)
            else:
                # 计算每个特征的均值作为新中心
                n_features = len(data[0])
                new_center = [sum(sample[f] for sample in cluster_samples) / len(cluster_samples) for f in range(n_features)]
            new_centers.append(new_center)

        # 检查是否收敛
        if prev_centers is not None:
            # 计算所有中心的总变化量
            total_change = sum(math.sqrt(sum((a - b) ** 2 for a, b in zip(prev, new))) for prev, new in zip(prev_centers, new_centers))
            if total_change < epsilon:
                print(f"迭代 {_ + 1} 次后收敛")
                break

        prev_centers = new_centers
        centers = new_centers

    else:
        print(f"达到最大迭代次数 {iteration}，未完全收敛")

    return labels, centers